package com.shinbada.common.tree;

import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Lists;
import com.google.common.collect.Multimap;
import com.shinbada.core.persistence.TreeEntity;
import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.lang.StringUtils;

import java.util.Comparator;
import java.util.List;

/**
 * 树结构构建工具类，主要分为三种方式：双层for循环、递归、Multimap+递归
 * 每种方式都有两个主要方法，普通构建和排序构建
 * 1.双层for循环时间复杂度n2,性能消耗较大，主要方法为 build buildSort
 * 2.递归时间复杂度也为n2,性能消耗较大，主要方法为 buildByRecursive buildByRecursiveSort
 * 3.Multimap+递归时间复杂度为2n,性能消耗较小，主要方法为 buildLevelTree buildLevelTreeSort
 *
 * @author initcap
 * @date Created in 2020/12/14 22:41.
 */
public class TreeUtil {

    private TreeUtil() {
        throw new IllegalArgumentException("util can not instance!");
    }

    /**
     * 将建立好的树结构数据，反解析会List集合
     *
     * @param treeList 属类型的数据
     * @param <T>      树集合
     * @return 返回铺开的集合
     */
    public static <T extends TreeEntity> List<T> treeToList(List<T> treeList) {
        List<T> resutList = Lists.newArrayList();
        if (CollectionUtils.isEmpty(treeList)) {
            return resutList;
        }
        for (int i = 0; i < treeList.size(); i++) {
            appendResultList(treeList.get(i), resutList);
        }
        return resutList;
    }

    private static <T extends TreeEntity> void appendResultList(T tree, List<T> resutList) {
        if (tree == null || StringUtils.isBlank(tree.getName())) {
            return;
        }
        resutList.add(tree);
        List<T> childrenList = tree.getChildren();
        for (int i = 0; childrenList != null && i < childrenList.size(); i++) {
            appendResultList(childrenList.get(i), resutList);
        }
    }

    /**
     * 通过level建树
     *
     * @param treeEntityList 所有数据集
     * @return 返回构建成树状结构的数据
     */
    public static <T extends TreeEntity> List<T> buildLevelTreeSort(List<T> treeEntityList) {
        if (CollectionUtils.isEmpty(treeEntityList)) {
            return Lists.newArrayList();
        }
        // level -> [dept1, dept2, ...] Map<String, List<Object>>
        //Multimap是用一个key，存储list的值，
        Multimap<String, T> levelNodeMap = ArrayListMultimap.create();
        // 拿到第一层级
        List<T> rootList = Lists.newArrayList();
        // 组装顶级集合和Multimap构建
        makeRootListAndMultimap(treeEntityList, levelNodeMap, rootList);
        // 递归生成树
        transformNodeTreeSort(rootList, levelNodeMap);
        return rootList;
    }

    /**
     * 组装顶级集合和Multimap
     *
     * @param treeNodeList 所有数据集合
     * @param levelNodeMap Multimap
     * @param rootList     顶级集合容器
     */
    private static <T extends TreeEntity> void makeRootListAndMultimap(List<T> treeNodeList, Multimap<String, T> levelNodeMap, List<T> rootList) {
        for (T node : treeNodeList) {
            // 将所有的值都以级别和值的方式存储起来，方便到时遍历
            levelNodeMap.put(TreeLevelUtil.currentLevel(node.getParentIds(), node.getId()), node);
            // 将顶级的进行收集
            if (node.getParentIds().split(TreeLevelUtil.SEPARATOR).length == 2) {
                rootList.add(node);
            }
        }
    }

    /**
     * level:0, 0, all 0->0/1,0/2
     * level:0/1
     * level:0/2
     *
     * @param rootList     当前层级集合
     * @param levelNodeMap 所有层级Map
     */
    private static <T extends TreeEntity> void transformNodeTreeSort(List<T> rootList, Multimap<String, T> levelNodeMap) {
        rootList.sort(Comparator.comparing(T::getSort));
        for (T node : rootList) {
            // 获取下一个所属层级
            String nextLevel = node.getParentIds();
            // 处理当前层级数据
            List<T> tempList = (List<T>) levelNodeMap.get(nextLevel);
            if (CollectionUtils.isNotEmpty(tempList)) {
                /*
                设置下一层部门,先进行清空，防止缓存问题，这里一定注意，
                1. 当数据每次都从数据库中读取时,内存地址不会相同
                2. 如果将所有数据存到缓存时，由于地址相同，会导致这里会携带上次的children问题，就会出现子集每次增长一倍,或许只是EhCache问题
                 */
                node.setChildren(Lists.newArrayList());

                for (T t : tempList) {
                    node.add(t);
                }
                List<T> list = node.getChildren();
                list.sort(Comparator.comparing(TreeEntity::getSort));
                transformNodeTreeSort(tempList, levelNodeMap);
            }
        }
    }

}
